package com.azure.code.graph.unionFind;

/**
 * 查并集：
 * 【连通】有三个性质:
 *   自反性： 节点p和q是连通的
 *   对称性： 如果节点p和q连通，那么q和p也连通
 *   传递性： 如果节点p和q连通，q和r连通，那么p和r也连通
 *
 *  这个UF的关键算法复杂度在与 find函数 union和connected的复杂度都是find函数造成的
 *  union构造的树有可能退化成链表 树的高度最坏的请求可能变成N
 *  有logN变成N
 *
 *  优化这个算法关键： 如何想办法避免树的不平衡
 */
public class UF {
    // 记录连通分量
    private int count;
    // 节点x的父节点 是 parent[x]
    private final int[] parent;

    /**
     * 构造函数，n为图的节点总数
     */
    public UF(int n){
        // 一开始互补连通
        this.count = n;
        parent = new int[n];
        // 父节点指正初始化指向自己
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ)
            return;

        // 将两颗树合并为一颗
        parent[rootP] = rootQ;
        // parent[rootQ] = rootP 也一样
        count--; // 两个分量合二为一
    }

    /**
     * 返回某个节点x的根节点
     */
    private int find(int x) {
        // 根节点 parent[x] = x
        while (parent[x] != x)
            x = parent[x];
        return x;
    }
    /* 返回当前的连通分量个数**/
    public int count(){
        return count;
    }

    /**
     * 判断p和q是否连通
     *
     * 如果节点p和q连通的话，他们一定拥有相同的根节点
     */
    public boolean connect(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

}
